# 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
#
# 来源：力扣（LeetCode）
# 链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
# 输入: [7,5,6,4]
# 输出: 5


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        return self.inverse(nums, 0, len(nums)-1)

    def inverse(self, nums, i, j):
        if i == j:
            return 0
        mid = (i + j) // 2
        return self.inverse(nums, i, mid) + self.inverse(nums, mid + 1, j) + self.merge(nums, i, mid, j)

    def merge(self, nums, i, mid, j):
        res = 0
        lst = []
        l, r = i, mid + 1
        while l <= mid and r <= j:
            if nums[l] > nums[r]:
                res += mid - l + 1
                lst.append(nums[r])
                r += 1
            else:
                lst.append(nums[l])
                l += 1
        while l <= mid:
            lst.append(nums[l])
            l += 1
        while r <= j:
            lst.append(nums[r])
            r += 1

        for idx in range(len(lst)):
            nums[idx + i] = lst[idx]
        return res